/*
题目链接：https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/
题目：1482.制作m束花所需的最少天数
提交时间：2024.9.17
二分，最小天数
*/

class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if(bloomDay.size()/k<m) return -1;   //说明花束不够做成花
        auto check=[&](int mid)->bool{
            int M=0;   //表示在mid下能够做的花束
            vector<int>open;  //表示在这个时间里，花是否为开
            for(int i=0;i<bloomDay.size();i++){                
                if(bloomDay[i]<=mid) open.push_back(1);   //花开
                else open.push_back(0);     //花未开
            }
            int c=0;
            for(int i=0;i<open.size();i++){
                if(open[i]==1) c++;
                if(open[i]==0) c=0;
                if(c==k) {M++;c=0;}
            }
            return M>=m;
        };
        int n=bloomDay.size();
        int l=bloomDay[0];         //花开花的最短时间
        int r=0;         //花开花的最长时间
        for(int i=0;i<n;i++) {
            l=min(l,bloomDay[i]);
            r=max(r,bloomDay[i]);
        }
        while(l<r){ 
            int mid=l+(r-l)/2;
            if(check(mid)) r=mid;   //在mid时间内能够制作的花束如果大于等于m，则r缩小
            else l=mid+1;
        }
        return l;
    }
};